﻿// 0818train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;

    if (root == nullptr)
        return result;

    queue<TreeNode*> bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty()) {
        int q_size = bfs_queue.size();

        vector<int> curr_vec;
        for (int i = 0; i < q_size; i++) {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            if (top_node != nullptr) {
                curr_vec.push_back(top_node->val);
            }

            if (top_node->left != nullptr)
                bfs_queue.push(top_node->left);

            if (top_node->right != nullptr)
                bfs_queue.push(top_node->right);
        }
        result.push_back(curr_vec);
    }
    return result;
    //levelOrder------
}


vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>>result;
    if (root == nullptr) return result;

	queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();
        vector<int>curr_vec;
        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            int val = top_node->val;
            curr_vec.push_back(val);

            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
            }
            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }
	        
        }

        result.push_back(curr_vec);
    }
    reverse(result.begin(), result.end());
    return result;

}



vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>>result;
    if (root == nullptr) return result;

    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    int level = 0;

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();
        vector<int>curr_vec;
        level++;
        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            curr_vec.push_back(top_node->val);

            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }

        }
        if (level%2==0)
        {
            reverse(curr_vec.begin(), curr_vec.end());
        }
        result.push_back(curr_vec);
    }

    return result;
}


vector<double> averageOfLevels(TreeNode* root) {
    vector<double>result;
    if (root == nullptr) return result;

    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    int level = 0;

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();
        vector<int>curr_vec;
        level++;
        for (int i = 0; i < q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            curr_vec.push_back(top_node->val);

            if (top_node->left != nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right != nullptr)
            {
                bfs_queue.push(top_node->right);
            }

        }
        double sum = 0;
        for (auto&num:curr_vec)
        {
            sum += num;
        }
        double average = sum / (curr_vec.size());
        result.push_back(average);
    }

    return result;
}


vector<int> rightSideView(TreeNode* root) {
    vector<int>result;
    if (root == nullptr) return result;

    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();

        
        for (int i = 0; i < q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            if (top_node->left != nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right != nullptr)
            {
                bfs_queue.push(top_node->right);
            }

            if (i==q_size-1)
            {
                result.push_back(top_node->val);
            }

        }
        
    }

    return result;
}


int findBottomLeftValue(TreeNode* root) {

    int result;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();

        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }

            if (i==0)
            {
                result = top_node->val;
            }

        }

    }
    return result;
}

/*
 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 */
vector<int> largestValues(TreeNode* root) {
    vector<int>result;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();

        vector<int>curr_vec;
        for (int i = 0; i < q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            if (top_node->left != nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right != nullptr)
            {
                bfs_queue.push(top_node->right);
            }
            curr_vec.push_back(top_node->val);
        }
        sort(curr_vec.begin(), curr_vec.end(), [](int a,int b)
        {
                return a > b;
        });
        result.push_back(curr_vec[0]);
    }
    return result;
}


/*
 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
 */
int maxLevelSum(TreeNode* root) {

    vector<pair<int,int>>sum_vec; //value,index
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    int level = 0;
    while (!bfs_queue.empty())
    {
        level++;
        vector<int>curr_vec;
        int q_size = bfs_queue.size();

        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            curr_vec.push_back(top_node->val);

            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
            }

            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }
        }

        int sum = 0;
        for (auto&num:curr_vec)
        {
            sum += num;
        }
        sum_vec.push_back(make_pair(sum, level));

    }
    sort(sum_vec.begin(), sum_vec.end(), [](pair<int,int>&a,pair<int,int>&b)
    {
        if (a.first==b.first)
        {
            return a.second < b.second;
        }
        return a.first > b.first;
    });
    return sum_vec[0].second;
}


TreeNode* BuildNode(vector<int>&tree_vec)
{
    if (tree_vec.empty() || tree_vec[0] == INT_MIN) return nullptr;

    TreeNode* root = new TreeNode(tree_vec[0]);
    queue<TreeNode*> q;
    q.push(root);

    //{ 1,2,3,4,null,5,6,null,null,7 }
    int i = 1;                 // 当前要处理的数组下标
    while (!q.empty() && i < tree_vec.size()) {
        TreeNode* cur = q.front(); q.pop();

        // 左孩子
        if (i < tree_vec.size() && tree_vec[i] != INT_MIN) {
            cur->left = new TreeNode(tree_vec[i]);
            q.push(cur->left);
        }
        ++i;

        // 右孩子
        if (i < tree_vec.size() && tree_vec[i] != INT_MIN) {
            cur->right = new TreeNode(tree_vec[i]);
            q.push(cur->right);
        }
        ++i;
    }
    return root;
}

int main()
{
    const int null = INT_MIN;   // 约定用 INT_MIN 代表空节点
    //vector<int>tree_vec = { 3,9,20,null,null,15,7 };
    //TreeNode* root = BuildNode(tree_vec.size(), tree_vec, 0);

    //vector<vector<int>>result = levelOrder(root);
    //vector<vector<int>>result = levelOrderBottom(root);
    //vector<vector<int>>result = zigzagLevelOrder(root);
    //vector<double>result = averageOfLevels(root);
    //vector<int>tree_vec = { 1,2,3,null,5,null,4 };
    //vector<int>tree_vec = { 1,2,3,4 };
    //TreeNode* root = BuildNode(tree_vec.size(), tree_vec, 0);
    //vector<int>result = rightSideView(root);
    //for (auto&mini_vec:result)
    //{
	   // for (auto&num: mini_vec)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}
    //for (auto&num:result)
    //{
    //    cout << num << ' ';
    //}
    //vector<int>tree_vec = { 1,2,3,4,null,5,6,null,null,7 };
    //
    //TreeNode* root = BuildNode(tree_vec);
    //cout << findBottomLeftValue(root);

    //root = [1,3,2,5,3,null,9]
    //vector<int>tree_vec = { 1,3,2,5,3,null,9 };
    //TreeNode* root = BuildNode(tree_vec);
    //vector<int>result = largestValues(root);

    //for (auto&num:result)
    //{
    //    cout << num << ' ';
    //}
    vector<int>tree_vec = { 1,7,0,7,-8,null,null };
    TreeNode* root = BuildNode(tree_vec);
    int result = maxLevelSum(root);
    cout << result;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
